# -*- coding: utf-8 -*-

"""剑指 Offer II 103. 最少的硬币数目
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
你可以认为每种硬币的数量是无限的。

示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

示例 2：
输入：coins = [2], amount = 3
输出：-1

示例 3：
输入：coins = [1], amount = 0
输出：0

示例 4：
输入：coins = [1], amount = 1
输出：1

示例 5：
输入：coins = [1], amount = 2
输出：2

提示：
1 <= coins.length <= 12
1 <= coins[i] <= 2^31 - 1
0 <= amount <= 10^4"""


class Solution:
    """回溯：每次都面临coins里面的任何一个选择，决策后进入下一回
    状态规划：过程在回溯，看结果，就是每次选择的哪一个coin
    f(amount) = min(f(amount-1), f(amount-2), f(amount-5))+1
    if amount in coins: return 1
    if amount <= 0: return float('inf')"""
    def coinChange(self, coins, amount: int) -> int:
        if amount == 0:
            return 0

        coins = set(coins)
        memory = dict((coin, 1) for coin in coins)
        
        def optimal(target):
            if target in coins:
                return 1
            
            if target < 0:
                return float('inf')
            
            mini = float('inf')
            for coin in coins:
                if (subterget := target-coin) in memory:
                    submini = memory[subterget]
                else:
                    # print('target:%s, coin:%s, subtarget:%s, submini:' % (target, coin, subterget))
                    submini = optimal(subterget)
                    memory[subterget] = submini
                # print('target:%s, coin:%s, subtarget:%s, submini:%s' % (target, coin, subterget, submini))
                mini = min(mini, submini+1)
            return mini
        answer = optimal(amount)
        if answer == float('inf'):
            answer = -1
        return answer


if __name__ == '__main__':
    so = Solution()
    # print(so.coinChange(coins = [1, 2, 5], amount = 11))
    # print(so.coinChange(coins = [2], amount = 3))
    # print(so.coinChange(coins = [1], amount = 0))
    # print(so.coinChange(coins = [1], amount = 1))
    # print(so.coinChange(coins = [1], amount = 2))
    print(so.coinChange(coins = [1, 2, 5], amount = 100))
